home *** CD-ROM | disk | FTP | other *** search
/ Technotools / Technotools (Chestnut CD-ROM)(1993).ISO / lang_c / bisonpcb / output.c < prev    next >
Text File  |  1987-02-13  |  25KB  |  1,269 lines
  1. /* Output the generated parsing program for bison,
  2.    Copyright (C) 1984, 1986 Bob Corbett and Free Software Foundation, Inc.
  3.   
  4. BISON is distributed in the hope that it will be useful, but WITHOUT ANY
  5. WARRANTY.  No author or distributor accepts responsibility to anyone
  6. for the consequences of using it or for whether it serves any
  7. particular purpose or works at all, unless he says so in writing.
  8. Refer to the BISON General Public License for full details.
  9.   
  10. Everyone is granted permission to copy, modify and redistribute BISON,
  11. but only under the conditions described in the BISON General Public
  12. License.  A copy of this license is supposed to have been given to you
  13. along with BISON so you can know your rights and responsibilities.  It
  14. should be in a file named COPYING.  Among other things, the copyright
  15. notice and this notice must be preserved on all copies.
  16.   
  17.  In other words, you are welcome to use, share and improve this program.
  18.  You are forbidden to forbid anyone else to use, share and improve
  19.  what you give them.   Help stamp out software-hoarding!  */
  20.  
  21. /* functions to output parsing data to various files.  Entries are:
  22.   
  23.   output_headers ()
  24.   
  25. Output constant strings to the beginning of certain files.
  26.   
  27.   output_trailers()
  28.   
  29. Output constant strings to the ends of certain files.
  30.   
  31.   output ()
  32.   
  33. Output the parsing tables and the parser code to ftable.
  34.   
  35. The parser tables consist of:  (starred ones needed only for the semantic parser)
  36.   
  37. yytranslate = vector mapping yylex's token numbers into bison's token numbers.
  38.   
  39. yytname = vector of string-names indexed by bison token number
  40.   
  41. yyrline = vector of line-numbers of all rules.  For yydebug printouts.
  42.   
  43. * yyrhs = vector of items of all rules.
  44.         This is exactly what ritems contains.
  45.   
  46. * yyprhs[r] = index in yyrhs of first item for rule r.
  47.   
  48. yyr1[r] = symbol number of symbol that rule r derives.
  49.   
  50. yyr2[r] = number of symbols composing right hand side of rule r.
  51.   
  52. * yystos[s] = the symbol number of the symbol that leads to state s.
  53.   
  54. yydefact[s] = default rule to reduce with in state s,
  55.           when yytable doesn't specify something else to do.
  56.           Zero means the default is an error.
  57.   
  58. yydefgoto[i] = default state to go to after a reduction of a rule that
  59.            generates variable ntokens + i, except when yytable
  60.            specifies something else to do.
  61.   
  62. yypact[s] = index in yytable of the portion describing state s.
  63.             The lookahed token's type is used to index that portion
  64.             to find out what to do.
  65.   
  66.         If the value in yytable is positive,
  67.         we shift the token and go to that state.
  68.   
  69.         If the value is negative, it is minus a rule number to reduce by.
  70.   
  71.         If the value is zero, the default action from yydefact[s] is used.
  72.   
  73. yypgoto[i] = the index in yytable of the portion describing 
  74.              what to do after reducing a rule that derives variable i + ntokens.
  75.              This portion is indexed by the parser state number
  76.          as of before the text for this nonterminal was read.
  77.          The value from yytable is the state to go to.
  78.   
  79. yytable = a vector filled with portions for different uses,
  80.           found via yypact and yypgoto.
  81.   
  82. yycheck = a vector indexed in parallel with yytable.
  83.       It indicates, in a roundabout way, the bounds of the
  84.       portion you are trying to examine.
  85.   
  86.       Suppose that the portion of yytable starts at index p
  87.       and the index to be examined within the portion is i.
  88.       Then if yycheck[p+i] != i, i is outside the bounds
  89.       of what is actually allocated, and the default
  90.       (from yydefact or yydefgoto) should be used.
  91.       Otherwise, yytable[p+i] should be used.
  92.   
  93. YYFINAL = the state number of the termination state.
  94. YYFLAG = most negative short int.  Used to flag ??
  95. YYNTBASE = ntokens.
  96.   
  97. */
  98.  
  99. /*
  100.  * Port to PC by Whit Gregg
  101.  *               Nourse, Gregg & Browne, Inc.
  102.  *         1 Horizon Road
  103.  *         Fort Lee, NJ  07024
  104.  */
  105.  
  106.  
  107. #include <stdio.h>
  108. #include <malloc.h>
  109. #include "machine.h"
  110. #include "new.h"
  111. #include "files.h"
  112. #include "gram.h"
  113. #include "state.h"
  114. #include "func.h"
  115.  
  116. #define    MAXTABLE 8080
  117.  
  118.  
  119. extern char **tags;
  120. extern int tokensetsize;
  121. extern int final_state;
  122. extern core **state_table;
  123. extern shifts **shift_table;
  124. extern errs **err_table;
  125. extern reductions **reduction_table;
  126. extern short *accessing_symbol;
  127. extern unsigned *LA;
  128. extern short *LAruleno;
  129. extern short *lookaheads;
  130. extern char *consistent;
  131. extern short *goto_map;
  132. extern short *from_state;
  133. extern short *to_state;
  134.  
  135.  
  136. static int nvectors;
  137. static int nentries;
  138. static short **froms;
  139. static short **tos;
  140. static short *tally;
  141. static short *width;
  142. static short *actrow;
  143. static short *state_count;
  144. static short *order;
  145. static short *base;
  146. static short *pos;
  147. static short *table;
  148. static short *check;
  149. static int lowzero;
  150. static int high;
  151.  
  152.  
  153.  
  154.  
  155. void
  156. output_headers()
  157. {                /* WG */
  158.     if (semantic_parser) {
  159.         fprintf(fguard, "\n#include %c%s%c\n", '"', attrsfile, '"');    /* WG */
  160.         fprintf(fguard, "extern int yyerror;\n");    /* WG */
  161.         fprintf(fguard, "extern int yycost;\n");    /* WG */
  162.         fprintf(fguard, "extern char * yymsg;\n");    /* WG */
  163.         fprintf(fguard, "extern YYSTYPE yyval;\n\n");    /* WG */
  164.         fprintf(fguard, "yyguard(n, yyvsp, yylsp)\n");    /* WG */
  165.         fprintf(fguard, "register int n;\n");    /* WG */
  166.         fprintf(fguard, "register YYSTYPE *yyvsp;\n");    /* WG */
  167.         fprintf(fguard, "register YYLTYPE *yylsp;\n");    /* WG */
  168.         fprintf(fguard, "{\n  yyerror = 0;\nyycost = 0;\n  yymsg = 0;\n");    /* WG */
  169.         fprintf(fguard, "switch (n)\n    {");    /* WG */
  170.  
  171. /*        fprintf(faction, "\n#include %c%s%c\n", '"', attrsfile, '"'); */
  172. /*        fprintf(faction, "extern YYSTYPE yyval;\n"); */
  173. /*        fprintf(faction, "extern int yychar;\n"); */
  174.         fprintf(faction, "yyaction(n, yyvsp, yylsp)\n");    /* WG */
  175.         fprintf(faction, "register int n;\n");    /* WG */
  176.         fprintf(faction, "register YYSTYPE *yyvsp;\n");    /* WG */
  177.         fprintf(faction, "register YYLTYPE *yylsp;\n");    /* WG */
  178.         fprintf(faction, "\t{\n\tswitch (n)\n\t\t{");    /* WG */
  179.         }
  180.     else {
  181.         fprintf(faction, "\n  switch (yyn) {\n");    /* WG */
  182.         }
  183.     }
  184.  
  185. void
  186. output_trailers()
  187. {                /* WG */
  188.     if (semantic_parser) {
  189.         fprintf(fguard, "\n    }\n}\n");
  190.         fprintf(faction, "\n    }\n}\n");
  191.         }
  192.     else
  193.         fprintf(faction, "\n}\n");
  194.     }
  195.  
  196.  
  197. void
  198. output()
  199. {                /* WG */
  200.     int c;
  201.  
  202.     /*
  203.      * output_token_defines(ftable);    /* JF put out token defines
  204.      * FIRST 
  205.      */
  206.     if (!semantic_parser) {    /* JF Put out other stuff */
  207.         rewind(fattrs);
  208.         while ((c = getc(fattrs)) != EOF)
  209.             putc((char) c, ftable);    /* WG */
  210.         }
  211.     /* output_program();    /* JF do it NOW */
  212.     if (semantic_parser)
  213.         fprintf(ftable, "#include \"%s\"\n", attrsfile);
  214.     fprintf(ftable, "#include <stdio.h>\n\n");
  215.  
  216.     free_itemsets();
  217.     output_defines();
  218.     output_token_translations();
  219.     if (semantic_parser)
  220.         output_gram();
  221.     FREE(ritem);
  222.     if (semantic_parser)
  223.         output_stos();
  224.     output_rule_data();
  225.     output_actions();
  226.     output_parser();
  227.     output_program();
  228.     }
  229.  
  230. void
  231. output_token_translations()
  232. {                /* WG */
  233.     register int i, j;
  234.  
  235. /*   register short *sp; JF unused */
  236.  
  237.     if (translations) {
  238.         fprintf(ftable, "\n#define YYTRANSLATE(x) (yytranslate[x])\n");
  239.  
  240.         if (ntokens < 127)    /* play it very safe; check maximum
  241.                      * element value.  */
  242.             fprintf(ftable, "\nstatic char yytranslate[] = {     0");
  243.         else
  244.             fprintf(ftable, "\nstatic short yytranslate[] = {     0");
  245.  
  246.         j = 10;
  247.         for (i = 1; i <= max_user_token_number; i++) {
  248.             putc(',', ftable);
  249.  
  250.             if (j >= 10) {
  251.                 putc('\n', ftable);
  252.                 j = 1;
  253.                 }
  254.             else {
  255.                 j++;
  256.                 }
  257.  
  258.             fprintf(ftable, "%6d", token_translations[i]);
  259.             }
  260.  
  261.         fprintf(ftable, "\n};\n");
  262.         }
  263.     else {
  264.         fprintf(ftable, "\n#define YYTRANSLATE(x) (x)\n");
  265.         }
  266.     }
  267.  
  268.  
  269.  
  270. void
  271. output_gram()
  272. {                /* WG */
  273.     register int i;
  274.     register int j;
  275.     register short *sp;
  276.  
  277.     fprintf(ftable, "\nstatic short yyprhs[] = {     0");
  278.  
  279.     j = 10;
  280.     for (i = 1; i <= nrules; i++) {
  281.         putc(',', ftable);
  282.  
  283.         if (j >= 10) {
  284.             putc('\n', ftable);
  285.             j = 1;
  286.             }
  287.         else {
  288.             j++;
  289.             }
  290.  
  291.         fprintf(ftable, "%6d", rrhs[i]);
  292.         }
  293.  
  294.     fprintf(ftable, "\n};\n\nstatic short yyrhs[] = {%6d", ritem[0]);
  295.  
  296.     j = 10;
  297.     for (sp = ritem + 1; *sp; sp++) {
  298.         putc(',', ftable);
  299.  
  300.         if (j >= 10) {
  301.             putc('\n', ftable);
  302.             j = 1;
  303.             }
  304.         else {
  305.             j++;
  306.             }
  307.  
  308.         if (*sp > 0)
  309.             fprintf(ftable, "%6d", *sp);
  310.         else
  311.             fprintf(ftable, "     0");
  312.         }
  313.  
  314.     fprintf(ftable, "\n};\n");
  315.     }
  316.  
  317.  
  318.  
  319. void
  320. output_stos()
  321. {                /* WG */
  322.     register int i;
  323.     register int j;
  324.  
  325.     fprintf(ftable, "\nstatic short yystos[] = {     0");
  326.  
  327.     j = 10;
  328.     for (i = 1; i < nstates; i++) {
  329.         putc(',', ftable);
  330.  
  331.         if (j >= 10) {
  332.             putc('\n', ftable);
  333.             j = 1;
  334.             }
  335.         else {
  336.             j++;
  337.             }
  338.  
  339.         fprintf(ftable, "%6d", accessing_symbol[i]);
  340.         }
  341.  
  342.     fprintf(ftable, "\n};\n");
  343.     }
  344.  
  345.  
  346.  
  347. void
  348. output_rule_data()
  349. {                /* WG */
  350.     register int i;
  351.     register int j;
  352.  
  353.     fprintf(ftable, "\nstatic short yyrline[] = {     0");
  354.  
  355.     j = 10;
  356.     for (i = 1; i <= nrules; i++) {
  357.         putc(',', ftable);
  358.  
  359.         if (j >= 10) {
  360.             putc('\n', ftable);
  361.             j = 1;
  362.             }
  363.         else {
  364.             j++;
  365.             }
  366.  
  367.         fprintf(ftable, "%6d", rline[i]);
  368.         }
  369.  
  370.     fprintf(ftable, "\n};\n\nstatic char * yytname[] = {     0");
  371.  
  372.     j = 10;
  373.     for (i = 1; i <= ntokens; i++) {
  374.         register char *p;
  375.  
  376.         putc(',', ftable);
  377.  
  378.         if (j >= 10) {
  379.             putc('\n', ftable);
  380.             j = 1;
  381.             }
  382.         else {
  383.             j++;
  384.             }
  385.  
  386.         putc('\"', ftable);
  387.  
  388.         for (p = tags[i]; *p; p++)
  389.             if (*p == '"' || *p == '\\')
  390.                 fprintf(ftable, "\\%c", *p);
  391.             else if (*p == '\n')
  392.                 fprintf(ftable, "\\n");
  393.             else if (*p == '\t')
  394.                 fprintf(ftable, "\\t");
  395.             else if (*p == '\b')
  396.                 fprintf(ftable, "\\b");
  397.             else if (*p < 040 || *p >= 0177)
  398.                 fprintf(ftable, "\\%03o", *p);
  399.             else
  400.                 putc(*p, ftable);
  401.  
  402.         putc('\"', ftable);
  403.         }
  404.  
  405.     fprintf(ftable, "\n};\n\nstatic short yyr1[] = {     0");
  406.  
  407.     j = 10;
  408.     for (i = 1; i <= nrules; i++) {
  409.         putc(',', ftable);
  410.  
  411.         if (j >= 10) {
  412.             putc('\n', ftable);
  413.             j = 1;
  414.             }
  415.         else {
  416.             j++;
  417.             }
  418.  
  419.         fprintf(ftable, "%6d", rlhs[i]);
  420.         }
  421.  
  422.     FREE(rlhs + 1);
  423.  
  424.     fprintf(ftable, "\n};\n\nstatic short yyr2[] = {     0");
  425.  
  426.     j = 10;
  427.     for (i = 1; i < nrules; i++) {
  428.         putc(',', ftable);
  429.  
  430.         if (j >= 10) {
  431.             putc('\n', ftable);
  432.             j = 1;
  433.             }
  434.         else {
  435.             j++;
  436.             }
  437.  
  438.         fprintf(ftable, "%6d", rrhs[i + 1] - rrhs[i] - 1);
  439.         }
  440.  
  441.     putc(',', ftable);
  442.     if (j >= 10)
  443.         putc('\n', ftable);
  444.  
  445.     fprintf(ftable, "%6d\n};\n", nitems - rrhs[nrules] - 1);
  446.     FREE(rrhs + 1);
  447.     }
  448.  
  449.  
  450.  
  451. void
  452. output_defines()
  453. {                /* WG */
  454.     fprintf(ftable, "\n\n#define\tYYFINAL\t\t%d\n", final_state);
  455.     fprintf(ftable, "#define\tYYFLAG\t\t%d\n", MINSHORT);
  456.     fprintf(ftable, "#define\tYYNTBASE\t%d\n", ntokens);
  457.     }
  458.  
  459.  
  460.  
  461. /* compute and output yydefact, yydefgoto, yypact, yypgoto, yytable and yycheck.  */
  462.  
  463. void
  464. output_actions()
  465. {                /* WG */
  466.     nvectors = nstates + nvars;
  467.  
  468.     froms = NEW2(nvectors, short *);
  469.     tos = NEW2(nvectors, short *);
  470.     tally = NEW2(nvectors, short);
  471.     width = NEW2(nvectors, short);
  472.  
  473.     token_actions();
  474.     free_shifts();
  475.     free_reductions();
  476.     FREE(lookaheads);
  477.     FREE(LA);
  478.     FREE(LAruleno);
  479.     FREE(accessing_symbol);
  480.  
  481.     goto_actions();
  482.     FREE(goto_map + ntokens);
  483.     FREE(from_state);
  484.     FREE(to_state);
  485.  
  486.     sort_actions();
  487.     pack_table();
  488.     output_base();
  489.     output_table();
  490.     output_check();
  491.     }
  492.  
  493.  
  494.  
  495. /* figure out the actions for the specified state, indexed by lookahead token type.
  496.   
  497.    The yydefact table is output now.  The detailed info
  498.    is saved for putting into yytable later.  */
  499.  
  500. void
  501. token_actions()
  502. {                /* WG */
  503.     register int i;
  504.     register int j;
  505.     register int k;
  506.  
  507.     actrow = NEW2(ntokens, short);
  508.  
  509.     k = action_row(0);
  510.     fprintf(ftable, "\nstatic short yydefact[] = {%6d", k);
  511.     save_row(0);
  512.  
  513.     j = 10;
  514.     for (i = 1; i < nstates; i++) {
  515.         putc(',', ftable);
  516.  
  517.         if (j >= 10) {
  518.             putc('\n', ftable);
  519.             j = 1;
  520.             }
  521.         else {
  522.             j++;
  523.             }
  524.  
  525.         k = action_row(i);
  526.         fprintf(ftable, "%6d", k);
  527.         save_row(i);
  528.         }
  529.  
  530.     fprintf(ftable, "\n};\n");
  531.     FREE(actrow);
  532.     }
  533.  
  534.  
  535.  
  536. /* Decide what to do for each type of token if seen as the lookahead token in specified state.
  537.    The value returned is used as the default action (yydefact) for the state.
  538.    In addition, actrow is filled with what to do for each kind of token,
  539.    index by symbol number, with zero meaning do the default action.
  540.    The value MINSHORT, a very negative number, means this situation
  541.    is an error.  The parser recognizes this value specially.
  542.   
  543.    This is where conflicts are resolved.  The loop over lookahead rules
  544.    considered lower-numbered rules last, and the last rule considered that likes
  545.    a token gets to handle it.  */
  546.  
  547. int
  548. action_row(state)
  549.     int state;
  550. {
  551.     register int i;
  552.     register int j;
  553.     register int k;
  554.     register int m;
  555.     register int n;
  556.     register int count;
  557.     register int default_rule;
  558.     register int nreds;
  559.     register int max;
  560.     register int rule;
  561.     register int shift_state;
  562.     register int symbol;
  563.     register unsigned mask;
  564.     register unsigned *wordp;
  565.     register reductions *redp;
  566.     register shifts *shiftp;
  567.     register errs *errp;
  568.     int nodefault = 0;    /* set nonzero to inhibit having any default
  569.                  * reduction */
  570.  
  571.     for (i = 0; i < ntokens; i++)
  572.         actrow[i] = 0;
  573.  
  574.     default_rule = 0;
  575.     nreds = 0;
  576.     redp = reduction_table[state];
  577.  
  578.     if (redp) {
  579.         nreds = redp->nreds;
  580.  
  581.         if (nreds >= 1) {
  582.             /*
  583.              * loop over all the rules available here which
  584.              * require lookahead 
  585.              */
  586.             m = lookaheads[state];
  587.             n = lookaheads[state + 1];
  588.  
  589.             for (i = n - 1; i >= m; i--) {
  590.                 rule = -LAruleno[i];
  591.                 wordp = LA + i * tokensetsize;
  592.                 mask = 1;
  593.  
  594.                 /*
  595.                  * and find each token which the rule finds
  596.                  * acceptable to come next 
  597.                  */
  598.                 for (j = 0; j < ntokens; j++) {
  599.                     /*
  600.                      * and record this rule as the rule
  601.                      * to use if that token follows.  
  602.                      */
  603.                     if (mask & *wordp)
  604.                         actrow[j] = rule;
  605.  
  606.                     mask <<= 1;
  607.                     if (mask == 0) {
  608.                         mask = 1;
  609.                         wordp++;
  610.                         }
  611.                     }
  612.                 }
  613.             }
  614.         }
  615.  
  616.     shiftp = shift_table[state];
  617.  
  618.     /*
  619.      * now see which tokens are allowed for shifts in this state. For
  620.      * them, record the shift as the thing to do.  So shift is preferred
  621.      * to reduce.  
  622.      */
  623.  
  624.     if (shiftp) {
  625.         k = shiftp->nshifts;
  626.  
  627.         for (i = 0; i < k; i++) {
  628.             shift_state = shiftp->shifts[i];
  629.             if (!shift_state)
  630.                 continue;
  631.  
  632.             symbol = accessing_symbol[shift_state];
  633.  
  634.             if (ISVAR(symbol))
  635.                 break;
  636.  
  637.             actrow[symbol] = shift_state;
  638.  
  639.             /*
  640.              * do not use any default reduction if there is a
  641.              * shift for error 
  642.              */
  643.  
  644.             if (symbol == error_token_number)
  645.                 nodefault = 1;
  646.             }
  647.         }
  648.  
  649.     errp = err_table[state];
  650.  
  651.     /*
  652.      * See which tokens are an explicit error in this state (due to
  653.      * %nonassoc).  For them, record MINSHORT as the action.  
  654.      */
  655.  
  656.     if (errp) {
  657.         k = errp->nerrs;
  658.  
  659.         for (i = 0; i < k; i++) {
  660.             symbol = errp->errs[i];
  661.             actrow[symbol] = MINSHORT;
  662.             }
  663.         }
  664.  
  665.     /*
  666.      * now find the most common reduction and make it the default action
  667.      * for this state.  
  668.      */
  669.  
  670.     if (nreds >= 1 && !nodefault) {
  671.         if (consistent[state])
  672.             default_rule = redp->rules[0];
  673.         else {
  674.             max = 0;
  675.             for (i = m; i < n; i++) {
  676.                 count = 0;
  677.                 rule = -LAruleno[i];
  678.  
  679.                 for (j = 0; j < ntokens; j++) {
  680.                     if (actrow[j] == rule)
  681.                         count++;
  682.                     }
  683.  
  684.                 if (count > max) {
  685.                     max = count;
  686.                     default_rule = rule;
  687.                     }
  688.                 }
  689.  
  690.             /*
  691.              * actions which match the default are replaced with
  692.              * zero, which means "use the default" 
  693.              */
  694.  
  695.             if (max > 0) {
  696.                 for (j = 0; j < ntokens; j++) {
  697.                     if (actrow[j] == default_rule)
  698.                         actrow[j] = 0;
  699.                     }
  700.  
  701.                 default_rule = -default_rule;
  702.                 }
  703.             }
  704.         }
  705.  
  706.     /*
  707.      * If have no default rule, the default is an error. So replace any
  708.      * action which says "error" with "use default".  
  709.      */
  710.  
  711.     if (default_rule == 0)
  712.         for (j = 0; j < ntokens; j++) {
  713.             if (actrow[j] == MINSHORT)
  714.                 actrow[j] = 0;
  715.             }
  716.  
  717.     return (default_rule);
  718.     }
  719.  
  720.  
  721.  
  722. void
  723. save_row(state)            /* WG */
  724.     int state;
  725. {
  726.     register int i;
  727.     register int count;
  728.     register short *sp;
  729.     register short *sp1;
  730.     register short *sp2;
  731.  
  732.     count = 0;
  733.     for (i = 0; i < ntokens; i++) {
  734.         if (actrow[i] != 0)
  735.             count++;
  736.         }
  737.  
  738.     if (count == 0)
  739.         return;
  740.  
  741.     froms[state] = sp1 = sp = NEW2(count, short);
  742.     tos[state] = sp2 = NEW2(count, short);
  743.  
  744.     for (i = 0; i < ntokens; i++) {
  745.         if (actrow[i] != 0) {
  746.             *sp1++ = i;
  747.             *sp2++ = actrow[i];
  748.             }
  749.         }
  750.  
  751.     tally[state] = count;
  752.     width[state] = sp1[-1] - sp[0] + 1;
  753.     }
  754.  
  755.  
  756.  
  757. /* figure out what to do after reducing with each rule,
  758.    depending on the saved state from before the beginning
  759.    of parsing the data that matched this rule.
  760.   
  761.    The yydefgoto table is output now.  The detailed info
  762.    is saved for putting into yytable later.  */
  763.  
  764. void
  765. goto_actions()
  766. {                /* WG */
  767.     register int i;
  768.     register int j;
  769.     register int k;
  770.  
  771.     state_count = NEW2(nstates, short);
  772.  
  773.     k = default_goto(ntokens);
  774.     fprintf(ftable, "\nstatic short yydefgoto[] = {%6d", k);
  775.     save_column(ntokens, k);
  776.  
  777.     j = 10;
  778.     for (i = ntokens + 1; i < nsyms; i++) {
  779.         putc(',', ftable);
  780.  
  781.         if (j >= 10) {
  782.             putc('\n', ftable);
  783.             j = 1;
  784.             }
  785.         else {
  786.             j++;
  787.             }
  788.  
  789.         k = default_goto(i);
  790.         fprintf(ftable, "%6d", k);
  791.         save_column(i, k);
  792.         }
  793.  
  794.     fprintf(ftable, "\n};\n");
  795.     FREE(state_count);
  796.     }
  797.  
  798.  
  799.  
  800. int
  801. default_goto(symbol)
  802.     int symbol;
  803. {
  804.     register int i;
  805.     register int m;
  806.     register int n;
  807.     register int default_state;
  808.     register int max;
  809.  
  810.     m = goto_map[symbol];
  811.     n = goto_map[symbol + 1];
  812.  
  813.     if (m == n)
  814.         return (-1);
  815.  
  816.     for (i = 0; i < nstates; i++)
  817.         state_count[i] = 0;
  818.  
  819.     for (i = m; i < n; i++)
  820.         state_count[to_state[i]]++;
  821.  
  822.     max = 0;
  823.     default_state = -1;
  824.  
  825.     for (i = 0; i < nstates; i++) {
  826.         if (state_count[i] > max) {
  827.             max = state_count[i];
  828.             default_state = i;
  829.             }
  830.         }
  831.  
  832.     return (default_state);
  833.     }
  834.  
  835.  
  836.  
  837. void
  838. save_column(symbol, default_state)    /* WG */
  839.     int symbol;
  840.     int default_state;
  841. {
  842.     register int i;
  843.     register int m;
  844.     register int n;
  845.     register short *sp;
  846.     register short *sp1;
  847.     register short *sp2;
  848.     register int count;
  849.     register int symno;
  850.  
  851.     m = goto_map[symbol];
  852.     n = goto_map[symbol + 1];
  853.  
  854.     count = 0;
  855.     for (i = m; i < n; i++) {
  856.         if (to_state[i] != default_state)
  857.             count++;
  858.         }
  859.  
  860.     if (count == 0)
  861.         return;
  862.  
  863.     symno = symbol - ntokens + nstates;
  864.  
  865.     froms[symno] = sp1 = sp = NEW2(count, short);
  866.     tos[symno] = sp2 = NEW2(count, short);
  867.  
  868.     for (i = m; i < n; i++) {
  869.         if (to_state[i] != default_state) {
  870.             *sp1++ = from_state[i];
  871.             *sp2++ = to_state[i];
  872.             }
  873.         }
  874.  
  875.     tally[symno] = count;
  876.     width[symno] = sp1[-1] - sp[0] + 1;
  877.     }
  878.  
  879.  
  880.  
  881. /* the next few functions decide how to pack 
  882.    the actions and gotos information into yytable. */
  883.  
  884. void
  885. sort_actions()
  886. {                /* WG */
  887.     register int i;
  888.     register int j;
  889.     register int k;
  890.     register int t;
  891.     register int w;
  892.  
  893.     order = NEW2(nvectors, short);
  894.     nentries = 0;
  895.  
  896.     for (i = 0; i < nvectors; i++) {
  897.         if (tally[i] > 0) {
  898.             t = tally[i];
  899.             w = width[i];
  900.             j = nentries - 1;
  901.  
  902.             while (j >= 0 && (width[order[j]] < w))
  903.                 j--;
  904.  
  905.             while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
  906.                 j--;
  907.  
  908.             for (k = nentries - 1; k > j; k--)
  909.                 order[k + 1] = order[k];
  910.  
  911.             order[j + 1] = i;
  912.             nentries++;
  913.             }
  914.         }
  915.     }
  916.  
  917.  
  918.  
  919. void
  920. pack_table()
  921. {                /* WG */
  922.     register int i;
  923.     register int place;
  924.     register int state;
  925.  
  926.     base = NEW2(nvectors, short);
  927.     pos = NEW2(nentries, short);
  928.     table = NEW2(MAXTABLE, short);
  929.     check = NEW2(MAXTABLE, short);
  930.  
  931.     lowzero = 0;
  932.     high = 0;
  933.  
  934.     for (i = 0; i < nvectors; i++)
  935.         base[i] = MINSHORT;
  936.  
  937.     for (i = 0; i < MAXTABLE; i++)
  938.         check[i] = -1;
  939.  
  940.     for (i = 0; i < nentries; i++) {
  941.         state = matching_state(i);
  942.  
  943.         if (state < 0)
  944.             place = pack_vector(i);
  945.         else
  946.             place = base[state];
  947.  
  948.         pos[i] = place;
  949.         base[order[i]] = place;
  950.         }
  951.  
  952.     for (i = 0; i < nvectors; i++) {
  953.         FREE(froms[i]);
  954.         FREE(tos[i]);
  955.         }
  956.  
  957.     FREE(froms);
  958.     FREE(tos);
  959.     FREE(pos);
  960.     }
  961.  
  962.  
  963.  
  964. int
  965. matching_state(vector)
  966.     int vector;
  967. {
  968.     register int i;
  969.     register int j;
  970.     register int k;
  971.     register int t;
  972.     register int w;
  973.     register int match;
  974.     register int prev;
  975.  
  976.     i = order[vector];
  977.     if (i >= nstates)
  978.         return (-1);
  979.  
  980.     t = tally[i];
  981.     w = width[i];
  982.  
  983.     for (prev = vector - 1; prev >= 0; prev--) {
  984.         j = order[prev];
  985.         if (width[j] != w || tally[j] != t)
  986.             return (-1);
  987.  
  988.         match = 1;
  989.         for (k = 0; match && k < t; k++) {
  990.             if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
  991.                 match = 0;
  992.             }
  993.  
  994.         if (match)
  995.             return (j);
  996.         }
  997.  
  998.     return (-1);
  999.     }
  1000.  
  1001.  
  1002.  
  1003. int
  1004. pack_vector(vector)
  1005.     int vector;
  1006. {
  1007.     register int i;
  1008.     register int j;
  1009.     register int k;
  1010.     register int t;
  1011.     register int loc;
  1012.     register int ok;
  1013.     register short *from;
  1014.     register short *to;
  1015.  
  1016.     i = order[vector];
  1017.     t = tally[i];
  1018.  
  1019.     if (t == 0)
  1020.         berror("pack_vector");
  1021.  
  1022.     from = froms[i];
  1023.     to = tos[i];
  1024.  
  1025.     for (j = lowzero - from[0]; j < MAXTABLE; j++) {
  1026.         ok = 1;
  1027.  
  1028.         for (k = 0; ok && k < t; k++) {
  1029.             loc = j + from[k];
  1030.             if (loc > MAXTABLE)
  1031.                 fatals("maximum table size (%d) exceeded", MAXTABLE);
  1032.  
  1033.             if (table[loc] != 0)
  1034.                 ok = 0;
  1035.             }
  1036.  
  1037.         for (k = 0; ok && k < vector; k++) {
  1038.             if (pos[k] == j)
  1039.                 ok = 0;
  1040.             }
  1041.  
  1042.         if (ok) {
  1043.             for (k = 0; k < t; k++) {
  1044.                 loc = j + from[k];
  1045.                 table[loc] = to[k];
  1046.                 check[loc] = from[k];
  1047.                 }
  1048.  
  1049.             while (table[lowzero] != 0)
  1050.                 lowzero++;
  1051.  
  1052.             if (loc > high)
  1053.                 high = loc;
  1054.  
  1055.             return (j);
  1056.             }
  1057.         }
  1058.  
  1059.     berror("pack_vector");
  1060.     return 0;        /* JF keep lint happy */
  1061.     }
  1062.  
  1063.  
  1064.  
  1065. /* the following functions output yytable, yycheck
  1066.    and the vectors whose elements index the portion starts */
  1067.  
  1068. void
  1069. output_base()
  1070. {                /* WG */
  1071.     register int i;
  1072.     register int j;
  1073.  
  1074.     fprintf(ftable, "\nstatic short yypact[] = {%6d", base[0]);
  1075.  
  1076.     j = 10;
  1077.     for (i = 1; i < nstates; i++) {
  1078.         putc(',', ftable);
  1079.  
  1080.         if (j >= 10) {
  1081.             putc('\n', ftable);
  1082.             j = 1;
  1083.             }
  1084.         else {
  1085.             j++;
  1086.             }
  1087.  
  1088.         fprintf(ftable, "%6d", base[i]);
  1089.         }
  1090.  
  1091.     fprintf(ftable, "\n};\n\nstatic short yypgoto[] = {%6d", base[nstates]);
  1092.  
  1093.     j = 10;
  1094.     for (i = nstates + 1; i < nvectors; i++) {
  1095.         putc(',', ftable);
  1096.  
  1097.         if (j >= 10) {
  1098.             putc('\n', ftable);
  1099.             j = 1;
  1100.             }
  1101.         else {
  1102.             j++;
  1103.             }
  1104.  
  1105.         fprintf(ftable, "%6d", base[i]);
  1106.         }
  1107.  
  1108.     fprintf(ftable, "\n};\n");
  1109.     FREE(base);
  1110.     }
  1111.  
  1112.  
  1113.  
  1114. void
  1115. output_table()
  1116. {                /* WG */
  1117.     register int i;
  1118.     register int j;
  1119.  
  1120.     fprintf(ftable, "\n\n#define\tYYLAST\t\t%d\n\n", high);
  1121.     fprintf(ftable, "\nstatic short yytable[] = {%6d", table[0]);
  1122.  
  1123.     j = 10;
  1124.     for (i = 1; i <= high; i++) {
  1125.         putc(',', ftable);
  1126.  
  1127.         if (j >= 10) {
  1128.             putc('\n', ftable);
  1129.             j = 1;
  1130.             }
  1131.         else {
  1132.             j++;
  1133.             }
  1134.  
  1135.         fprintf(ftable, "%6d", table[i]);
  1136.         }
  1137.  
  1138.     fprintf(ftable, "\n};\n");
  1139.     FREE(table);
  1140.     }
  1141.  
  1142.  
  1143.  
  1144. void
  1145. output_check()
  1146. {                /* WG */
  1147.     register int i;
  1148.     register int j;
  1149.  
  1150.     fprintf(ftable, "\nstatic short yycheck[] = {%6d", check[0]);
  1151.  
  1152.     j = 10;
  1153.     for (i = 1; i <= high; i++) {
  1154.         putc(',', ftable);
  1155.  
  1156.         if (j >= 10) {
  1157.             putc('\n', ftable);
  1158.             j = 1;
  1159.             }
  1160.         else {
  1161.             j++;
  1162.             }
  1163.  
  1164.         fprintf(ftable, "%6d", check[i]);
  1165.         }
  1166.  
  1167.     fprintf(ftable, "\n};\n");
  1168.     FREE(check);
  1169.     }
  1170.  
  1171.  
  1172.  
  1173. /* copy the parser code into the ftable file at the end.  */
  1174.  
  1175. void
  1176. output_parser()
  1177. {                /* WG */
  1178.     register int c;
  1179.  
  1180.     if (pure_parser)
  1181.         fprintf(ftable, "#define YYIMPURE 1\n\n");
  1182.     else
  1183.         fprintf(ftable, "#define YYPURE 1\n\n");
  1184.  
  1185.     /*
  1186.      * JF no longer needed 'cuz open_extra_files changes the currently
  1187.      * open parser from bison.simple to bison.hairy 
  1188.      */
  1189. /*  if (semantic_parser) fpars = fparser; else fpars = fparser1; */
  1190.  
  1191.     c = getc(fparser);
  1192.     while (c != EOF) {
  1193.         if (c == '$') {
  1194.             /*
  1195.              * JF don't #include the action file.  Stuff it right
  1196.              * in. 
  1197.              */
  1198.             rewind(faction);
  1199.             for (c = getc(faction); c != EOF; c = getc(faction))
  1200.                 putc((char) c, ftable);    /* WG */
  1201.             }
  1202.         else
  1203.             putc((char) c, ftable);    /* WG */
  1204.         c = getc(fparser);
  1205.         }
  1206.     }
  1207.  
  1208.  
  1209.  
  1210. void
  1211. output_program()
  1212. {                /* WG */
  1213.     register int c;
  1214.     extern int lineno;
  1215.  
  1216.     fprintf(ftable, "#line %d \"%s\"\n", lineno, infile);
  1217.  
  1218.     c = getc(finput);
  1219.     while (c != EOF) {
  1220.         putc((char) c, ftable);    /* WG */
  1221.         c = getc(finput);
  1222.         }
  1223.     }
  1224.  
  1225.  
  1226.  
  1227. void
  1228. free_itemsets()
  1229. {                /* WG */
  1230.     register core *cp, *cptmp;
  1231.  
  1232.     FREE(state_table);
  1233.  
  1234.     for (cp = first_state; cp; cp = cptmp) {
  1235.         cptmp = cp->next;
  1236.         FREE(cp);
  1237.         }
  1238.     }
  1239.  
  1240.  
  1241.  
  1242. void
  1243. free_shifts()
  1244. {                /* WG */
  1245.     register shifts *sp, *sptmp;    /* JF derefrenced freed ptr */
  1246.  
  1247.     FREE(shift_table);
  1248.  
  1249.     for (sp = first_shift; sp; sp = sptmp) {
  1250.         sptmp = sp->next;
  1251.         FREE(sp);
  1252.         }
  1253.     }
  1254.  
  1255.  
  1256.  
  1257. void
  1258. free_reductions()
  1259. {                /* WG */
  1260.     register reductions *rp, *rptmp;    /* JF fixed freed ptr */
  1261.  
  1262.     FREE(reduction_table);
  1263.  
  1264.     for (rp = first_reduction; rp; rp = rptmp) {
  1265.         rptmp = rp->next;
  1266.         FREE(rp);
  1267.         }
  1268.     }
  1269.